package test3.src;
import java.util.ArrayList;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class LinkedListProblem{

    //删除链表中所有值为value的元素
    public ListNode removeElements(ListNode head, int val) {
        //判断链表是否为空
            if (head==null){
                return null;
            }
            ListNode pre=head;
            ListNode cur=head.next;
            while(cur!=null){
                if (cur.val==val){
                    //出发删除操作，把cur给删掉
                    pre.next=cur.next;
                    //删除cur之后，需要移动cur指向下一个位置
                    cur=cur.next;
                }else{
                    //没有触发删除
                    //移动pre和cur的位置
                    pre=cur;
                    cur=cur.next;
                }
            }
            //最后判断头节点的删除情况
        if (head.val==val){
            head=head.next;
        }
        return head;
    }


    //反转链表
    public ListNode reverseList(ListNode head) {
        //1.判断链表为空
        if (head==null){
            return null;
        }
        //2.判断链表只有一个节点
        if(head.next==null){
            return head;
        }
        //3。处理一般的情况
        ListNode newHead=null;
        ListNode prev=null;
        ListNode cur=head;
        ListNode next=cur.next;
        while(cur!=null){
            //每次循环，都需要把next的位置记录下来，在进行后续的修改
            next = cur.next;
            //如果next已经是null，说明cur就是最后一个节点，让这个节点作为新的头节点
            if (next==null){
                newHead=cur;
            }
            //进行反转操作
            cur.next = prev;
            //更新prev和cur的指向
            prev=cur;
            cur=next;
        }
        return newHead;
    }

    //获取链表的长度
    public int size(ListNode head){
        int size=0;
        for (ListNode cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }
    //获取链表的中间节点
    public ListNode middleNode(ListNode head) {
        //1.链表为空
        if (head==null){
            return null;
        }
        //2.求链表的长度
        int size=size(head);
        int mid=size/2;
        ListNode cur=head;
        for (int i=0;i<mid;i++){
            cur=cur.next;
        }
        return cur;
    }

    //输出链表倒数第k个节点
    public int kthToLast(ListNode head, int k) {
        // 1. 判定链表为空, 判定 k 有效.
        if (head == null) {
            // 此处正常来说是要返回非法的值.
            // 要么返回 null
            // 要么是抛出异常.
            // 但是这两个做法在 OJ 中是不行的.
            // 实在没有别的非法值了, 就返回 0.
            return 0;
        }
        int size = size(head);
        if (k <= 0 || k > size(head)) {
            // 注意条件的边界, 要不要写 == , 需要代入数字判定.
            // k == 0 不行, 约定 k 必须从 1 开始 (题目的例子中给定隐式条件)
            // k == size 认为是可以的. 刚才数了一下, 长度为 5 的链表, 头节点元素, 倒数第 5 个.
            return 0;
        }
        // 3. 根据 k 和长度计算出要走的步数 (size - k)
        int step = size - k;
        ListNode cur=head;
        for (int i=0;i<step;i++){
            cur=cur.next;
    }
        return cur.val;
}

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. 判定链表为空
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 2. 准备两个引用指向两个链表.
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        // 3. 准备一个新的链表, 用于存放合并后的结果.
        //    同时也保存链表的尾巴. 后续都是尾插. 记录尾巴, 比较方便进行尾插的.
        //    此处如果使用 "带有傀儡节点" 的方式来实现尾插, 后续会更简单.
        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;
        // 4. 进入循环, 开始合并.
        while (cur1 != null && cur2 != null) {
            // 判定这两个引用较小的值.
            if (cur1.val < cur2.val) {
                // cur1 比较小, 插入到 newTail 之后.
                // 结果链表不为空链表. 尾插.
                newTail.next = cur1;
                // 插入完毕之后, 让 newTail 指向新的尾巴.
                newTail = cur1;
                // 更新 cur1 指向下一个节点.
                cur1 = cur1.next;
            } else {
                // cur2 比较小, 插入到 newTail 之后.
                newTail.next = cur2;
                newTail = cur2;
                // 更新 cur2 指向下一个节点.
                cur2 = cur2.next;
            }
        }
        // 5. 上述循环完毕, 意味着 cur1 或者 cur2 有一个已经遍历完了.
        //    只需要把剩余的节点, 挂到新链表末尾即可.
        if (cur1 != null) {
            // cur1 还有剩余, 挂到 newTail 之后.
            newTail.next = cur1;
        }
        if (cur2 != null) {
            // cur2 还有剩余, 挂到 newTail 之后.
            newTail.next = cur2;
        }
        // 6. 返回合并后的链表. newHead 指向的是傀儡节点. 真正的头结点是 newHead.next
        return newHead.next;
    }

    //链表分割
    //给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) {
            // 链表只有一个节点, 得到的结果还是本身.
            return pHead;
        }
        // 针对一般情况, 先创建两个链表.
        // 由于接下来都是尾插, 为了方便, 直接创建 tail 指向尾部节点, 并且创建傀儡节点, 简化逻辑.
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode largeTail = largeHead;
        // 遍历链表
        for (ListNode cur = pHead; cur != null; cur = cur.next) {
            if (cur.val < x) {
                // 把 cur 尾插到 smallTail 之后.
                smallTail.next = cur;
                smallTail = cur;
            } else {
                // 把 cur 尾插到 largeTail 之后.
                largeTail.next = cur;
                largeTail = cur;
            }
        }
        // 最后把 large 这个链表追加到 small 之后.
        // 把 large 链表的头结点(傀儡之后的节点), 使用 smallTail 的 next 指向.
        smallTail.next = largeHead.next;
        // 稳妥起见, 把 largeTail 的 next 指向 null. 避免出现 由于 largeTail next 不为空导致的链表出错.
        largeTail.next = null;
        return smallHead.next;
    }

    //链表的回文结构
    // 空间复杂度 O(N) 的版本.
    public boolean chkPalindrome2(ListNode A) {
        if (A == null) {
            // 空链表, 视为回文
            return true;
        }
        if (A.next == null) {
            // 只有一个节点, 也视为回文
            return true;
        }
        // 1. 把链表复制一份
        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;
        for (ListNode cur = A; cur != null; cur = cur.next) {
            ListNode newNode = new ListNode(cur.val);
            newTail.next = newNode;
            newTail = newNode;
        }
        // 傀儡节点不再使用了.
        newHead = newHead.next;

        // 2. 把复制的链表逆置
        ListNode prev = null;
        ListNode cur = newHead;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                newHead = cur;
            }
            // 关键操作
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 3. 比较两个链表是否相同
        ListNode cur1 = A;
        ListNode cur2 = newHead;
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) {
                // 出现不相等的情况, 一定不是回文.
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (cur1 == null && cur2 == null) {
            // 两个链表同时遍历完, 长度相同, 就是回文
            return true;
        }
        // 两个链表长度不同, 不是回文.
        return false;
    }
    //链表的回文结构
    // 空间复杂度 O(1) 的版本.
    public boolean chkPalindrome1(ListNode A) {
        if (A==null){
            return true;
        }
        if (A.next==null){
            return true;
        }
        int size=size(A);
        int step=size/2;
        ListNode B=A;
        for (int i=0;i<step;i++){
            B=B.next;
        }
        //此时B就指向中间节点
        //2.针对B这个链表进行逆置
        ListNode prev=null;
        ListNode cur=B;
        while(cur!=null){
            ListNode next=cur.next;
            if (next==null){
                // 此时cur就是新的头节点
                B=cur;
            }
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        //3. 比较 A 和 B 两个链表是否相同.
        ListNode cur1=A;
        ListNode cur2=B;
        while(cur1 != null && cur2 != null){
            if (cur1.val!=cur2.val){
                return false;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        // 不去考虑长度问题了. 如果节点是偶数个, 此时 A 的长度就是会比 B 多一个.
        return true;
    }

    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
    // 如果两个链表不存在相交节点，返回 null 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 判定空的情况先放一放, 先往后写, 再回头看是否需要判空
        int sizeA=size(headA);
        int sizeB=size(headB);
        // 2. 让长的链表的引用先往后走 长度差值 步.
        ListNode curA=headA;
        ListNode curB=headB;
        if (sizeA>sizeB){
            // A 链表先走, sizeA - sizeB 步.
            for (int i=0;i<sizeA-sizeB;i++){
                curA=curA.next;
            }
        }else{
            // B 链表先走, sizeB - sizeA 步.
            for (int i=0;i<sizeB-sizeA;i++){
                curB=curB.next;
            }
        }
        // 3. 再让两个引用同时出发, 往后各自走一步, 看什么时候两个引用指向同一个节点 (相遇), 此时的这个节点就是交点.
        while (curA!=null&&curB!=null){
            // 两个引用相遇了. 此时得到的这个节点就是链表的交点.
            if (curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }

    //给你一个链表的头节点 head ，判断链表中是否有环。
    public boolean hasCycle2(ListNode head) {
        // 朴素的做法: 使用 List 记录遍历过程中的每个节点.
        // 每次取到一个节点, 都先判定是否已经在 List 中出现过.
        // 如果出现过, 就是带环的.
        if (head==null){
            return false;
        }
        ArrayList<ListNode> list=new ArrayList<>();
        for (ListNode cur=head;cur!=null;cur=cur.next){
            if (list.contains(cur)){
                return true;
            }else{
                list.add(cur);
            }
        }
        return false;
    }
    public boolean hasCycle(ListNode head) {
        // 使用双引用, 一个快引用, 一个慢引用.
        // 初始情况下, 两个引用都指向 head.
        // 让快引用一次走两步, 慢引用一次走一步.
        // 判定是否会重合. 如果重合就是带环了.
        if (head==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        // 没有出发上述 return true, 反而是触发了 fast 为 null 或者 fast.next 为 null.
        // 此时链表无环的.
        return false;
    }

    //给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    public ListNode detectCycle(ListNode head) {
        if (head==null){
            return null;
        }
        // 1. 使用快慢指针, 找到相遇位置. 如果不相遇, 说明无环.
        ListNode slow=head;
        ListNode fast=head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 循环结束, 需要判定, 是因为 fast 和 slow 重合, 结束循环的, 还是因为 fast 为 null 结束循环的.
        if (fast==null||fast.next==null){
            // fast 为 null 或者 fast.next 为 null, 说明链表无环.
            return null;
        }
        // 2. 设置一个 cur1 , 从 head 出发, 设置 cur2 从交汇位置出发. 两个引用同时往前走.
        ListNode cur1=head;
        ListNode cur2=fast;
        // 这里的循环一定不会死循环的. 通过数学公式已经证明了, cur1 和 cur2 是必定会相遇.
        // 而且相遇的位置就是环的入口.
        while(cur1!=cur2){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        // 循环结束, 说明 cur1 和 cur2 相遇了.
        return cur1;
    }
}
